1. Field of the Invention
The present invention relates generally to methods and systems for processing image data, and more particularly, to methods and systems for computing complete surfaces from collections of coordinates representing points on an object's surface to generate images or for producing three-dimensional physical replicas or models of objects.
2. Description of the Related Art
The creation of three-dimensional digital objects by scanning real objects or scenes has become common practice in computer graphics applications, computer-aided design and manufacturing, urban planning, training simulations and building construction. Computer graphics applications include computer games, e-commerce and virtual museums, for example. Computer-aided design applications include scanning objects to be used as starting points for the design of new products. For example, features on existing objects can be numerically deleted and added to create new designs.
Computer-aided manufacturing applications include measuring an object to generate a physical replica using a three-dimensional hard copy device that produces objects by building layers of polymeric material, or sintering successive layers of metallic powders. Scans on the scale of the size of cities may be obtained for planning purposes such as assessing the impact of a new building or highway. In military applications, scanned cities or buildings may be used in virtual reality training simulations. In building construction, an existing building may be scanned to generate “as built” drawings to be used as a starting point for building remodeling. The following description has been restricted for convenience to techniques involving instruments that capture range images (in which each pixel value represents depth).
In general, a variety of techniques can be used to capture digital models of physical objects, including CAT scans and structure from motion applied to video sequences. Popular devices for capturing range images include laser triangulation systems (for objects less than a meter in largest dimension), laser time of flight systems (for objects up to a few hundred meters in size) and LIDAR (LIght Detection And Ranging), for scenes on the scale of the size of cities.
The basic operations necessary to create a digital model from a series of captured images may be as follows. After outliers (stray or unnecessary digital points) are removed from the range images, they are in the form of individual height-field meshes. A first step aligns these meshes into a single global coordinate system. In some systems this alignment is performed by tracking, for example, by a coordinate measurement machine for small-scale scanners, or by GPS (global positioning system) for large-scale scanners. In many systems, registration is performed by manual alignment. The alignment is then refined automatically using techniques such as the Iterative Closest Point (ICP) algorithm of Besl and McKay (See, “A method for registration of 3-D shapes”; by Besl, P. J. and McKay, H. D. in Patten Analysis and Machine Intelligence, IEEE Transactions, Vol. 14, Issue 2, February 1992, pp. 239-256), which is known in the art.
After registration, scans do not form a single surface, but often interpenetrate one another due to acquisition errors, primarily along the line-of-sight in each scan. These need to be corrected in a scan integration.
At the end of scan integration, there may be holes in the final surface, which are not physically present in the object. These holes are the result of the scanning device not being able to sample parts of objects. Areas may not be sampled if they are dark and so reflect little light, if they are partially hidden by another part of the object, or in the case of urban modeling, if objects such as buildings are hidden by trees, etc. These are artificial holes that result from the scanning process and are unacceptable in almost all applications that use 3D models.
In any computer graphics applications or visual simulation, large black regions on an object are unrealistic and distracting. In computer-aided design and manufacturing it is physically impossible to reproduce an object with an incomplete surface definition.
It should be noted that in addition to holes occurring because of problems with data collection, holes may also be created by users in a computer aided-design system. In editing an object a user may want to delete a feature such as a handle or embossed pattern that was part of the original object. In this case also, a method for filling the hole that is left is needed.
Prior art methods for hole-filling are either implemented as a post-processing operation, applied after surface reconstruction, or they are integrated into a surface reconstruction technique. For hole-filling as post-processing, a widely used approach is to triangulate each connected component of the surface's boundary, which results in filling each hole with a patch that has the topology of a disk. This works well for simple holes in almost flat surfaces, but for more complex cases it results in self-intersecting surfaces.
Two methods attempt to avoid this problem, Davis et al., 3DPVT, Padua, June 2002, in “Filling Holes in Complex Surfaces Using Volumetric Diffusion” developed a technique for filling holes by using a diffusion operation to expand the “signed distance function” defined by the existing points to complete a volumetric representation of the surface. But, the method lacks control over properties of the surface, like curvature, which leads to surfaces not matching the topology of the object being modeled (scanned) in some cases.
Correct topology may require additional information from the user, such as the original lines-of-sight used in scanning which may not be available, or in the case of holes created by a user modifying an object in a computer-aided design may never have existed.
Verdera et al., IEEE ICIP, September 2003, in “Inpainting Surface Holes” represented the surface of interest as the zero level-set of a function and then used a system of coupled geometric partial differential equations to smoothly continue the surface into the hole. This method suffers from the same lack of user control as the volumetric diffusion method. It also requires that the user provide the line-of-sight information that may not be available.
For hole-filling techniques integrated into surface reconstruction methods, Curless et al in “A Volumetric Method for Building Complex Models from Range Images”, ACM SIGGRAPH 1996, converts each model mesh into a signed distance function whose zero set is the observed surface, blends these distance functions together and extracts the zero set as the final surface. However, the method does not operate properly if the scanner lines of sight do not adequately cover the volume outside the object.
Carr et al., ACM SIGGRAPH 2001, in “Reconstruction and Representation of 3D Objects with Radial Basis Functions” fits a set of radial basis functions to the data, and a weighted sum of these functions forms a new function, a level set of which is the intended surface. The method rebuilds the entire surfaces based on radial basis functions, rather than just operating on the region near the holes. Consequently, this method is slow especially for large models. For large models, such as urban scenes or complex large works of art, the computational time is impractical for building a model in time to be used for the application.
Similarly, Dey and Goswami, Solid Modeling, June 2003, in “Tight Cocone: A Water-tight Surface Reconstructor” produce a model without holes by using an alternative technique for rebuilding the model from the original points. In their method, a 3 dimensional Delauney triangulation of the points is computed. The time to perform this calculation increases as N**2 for N points, making this approach not feasible for anything but relatively small point sets.
Therefore, a system and method are needed to fill in a surface in a hole left by inadequate data in a realistic manner and remain compatible with the original physical object. In addition, a system and method are needed for building a mesh for the points that are available in a scan, in a quick and efficient manner. The system and method also need to give the user easily specified parameters for operating on any remaining holes to produce a surface that is a faithful representation of the original object.